package org.example.SolutionNew003;

import java.util.*;

public class DoubleTree014 {
    public static void main(String[] args) {
        DoubleTree014 dt=new DoubleTree014();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.right = new TreeNode(4);
        root.left.left = new TreeNode(3);
        System.out.println(dt.lowestCommonAncestor(root,root.left.left,root.right.right).val);
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        //公共祖先，从根节点出发到最近的一定相同，最近的下一个就不同了
        List<TreeNode> ppath=new ArrayList<>();
        findThePath(root,p,ppath);
        List<TreeNode> qpath=new ArrayList<>();
        findThePath(root,q,qpath);
        TreeNode res=qpath.get(0);
        for(int i = 1; i< (Math.min(ppath.size(), qpath.size())); i++){
            if(ppath.get(i).val != qpath.get(i).val) return res;
            res=qpath.get(i);
        }
        return res;
    }

    public boolean findThePath(TreeNode root, TreeNode target,List<TreeNode> path) {
        if (root == null) return false;

        path.add(root);
        if (root == target) {
            return true;
        }

        if(findThePath(root.left,target,path)) return true;
        if(findThePath(root.right,target,path)) return true;
        path.remove(path.size()-1);
        return false;
    }

    TreeNode res=null;

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        findThePath(root,p,q);
        return res;
    }

    public boolean findThePath(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lb=findThePath(root.left,p,q);
        boolean rb=findThePath(root.right,p,q);
        if((lb && rb) || ((root.val == p.val || root.val == q.val)&&(lb||rb))){
            res=root;
        }
        return lb||rb||root.val==p.val||root.val==q.val;
    }

    //使用map存储每个节点的父节点，用set存储p/q到root的路径，然后遍历另一个节点获得最深的公共父节点
    Map<Integer,TreeNode> map=new HashMap<>();
    Set<Integer> set=new HashSet<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        map.put(root.val,null);
        dfs(root);
        while(p!=null){
            set.add(p.val);
            p=map.get(p.val);
        }
        while(q!=null){
            if(set.contains(q.val)){
                return q;
            }
            q=map.get(q.val);
        }
        return root;
    }

    public void dfs(TreeNode root) {
        if (root == null) return;
        if(root.left!=null){
            map.put(root.left.val,root);
            dfs(root.left);
        }
        if(root.right!=null){
            map.put(root.right.val,root);
            dfs(root.right);
        }
    }

}
